package com.data.basic.chapter07;

/** 基于二叉搜索树的map实现
 * Created by wangbing on 2018/5/16.
 */
public class BSTMap<K extends Comparable<K>,V> implements MyMap<K,V> {

    private class Node{
        /**
         * 二分搜索树的节点类
         */
        public K key;
        public V value;
        public Node left,right;

        public Node(K key,V value) {
            this.key = key;
            this.value = value;
            this.left = null;
            this.right = null;
        }
    }

    private Node root;
    private int size;

    public BSTMap() {
        root = null;
        size= 0;
    }

    public void add(K k, V v) {//二叉搜索树添加元素(key,value)
        root = add(root,k,v);

    }

    /**
     * 1.递归终止的条件
     */
// 向以node为根的二分搜索树中插入元素E，递归算法
// 返回插入新节点后二分搜索树的根------->将节点挂在二叉树下
    private Node add(Node node, K key,V value) {
//        1.递归终止的条件
        if (node==null){
            size++;
            return new Node(key, value);
        }
//      执行递归  重复元素不再添加
        if (key.compareTo(node.key)<0){
            node.left =  add(node.left,key,value);
        }else if(key.compareTo(node.key)>0){
            node.right = add(node.right,key,value);
        }else{// 新值覆盖旧值
            node.value = value;
        }
        return node;

    }

    public V remove(K k) {
        Node node = getNode(root,k);
        if (node!=null){
            root = remove(node,k);
            return node.value;
        }


        return null;
    }

    /**
     * 删除掉以node为根的二分搜索树中键为key的节点，递归算法
     * 返回删除节点后新的二分搜索树的根
     * @param node
     * @param key
     * @return
     */
    private Node remove(Node node, K key){//按照key来删除节点，并返回删除后的节点
        if (key.compareTo(node.key)<0){
            node.right = remove(node.right,key);
            return node;
        }else if (key.compareTo(node.key)>0){
            node.left = remove(node.left,key);
            return node;
        }else {
            if (node.right==null){
                Node leftNode = node.left;
                node.left = null;
                size--;
                return leftNode;
            }else if (node.left == null){
                Node rightNode = node.right;
                node.right = null;
                size--;
                return rightNode;
            }
            // 找到右子树的最小节点或者左子树的最大节点
            // 寻找右子树的最小值来替换这里的要删除的节点
            Node successor = minimum(node.right);
            successor.right = removeMin(node.right);// 返回的删除右子树的最小值之后的，右子树的根节点
            size++;// removeMin赋值给了successor，所以要加回来
            successor.left = node.left;


            node.left = node.right = null;
            size--;// 删除了节点的联系

            return successor;


        }


    }
    private Node minimum(Node node){//找到最小元素
        if (node.left==null){
            return node;
        }
        return minimum(node.left);

    }
    /**
     * 删除掉以node为根的二分搜索树中的最小节点
     * 返回删除节点后新的二分搜索树的根
     */
    private Node removeMin(Node node) {
        if (node.left==null){
            Node rightNode = node.right;
            node.right = null;
            size--;
            return rightNode;// 返回最小元素的右子树
        }
        node.left = removeMin(node.left);// 将最小元素的右孩子直接赋值给最小元素节点的父亲节点
        return node;

    }
    private Node maximum(Node node) {//找到最大元素
        if (node.right==null){
            return node;
        }
        return  maximum(node.right);
    }

    public boolean contains(K k) {//是否包含元素
        return getNode(root,k)!=null;
    }

    public V get(K k) {//获取元素
        Node node = getNode(root,k);
        return node==null?null:node.value;
    }
    // 返回以node为根节点的二分搜索树，key所在的节点
    private Node getNode(Node node,K key){
        if (node == null){
            return null;
        }
        if (key.compareTo(node.key)==0){
            return node;
        }
        else if (key.compareTo(node.key)<0){
            return getNode(node.right,key);
        }else {
            return getNode(node.left,key);
        }
    }

    public void set(K k, V v) {
        Node node = getNode(root,k);
        if (node==null){
            throw new IllegalArgumentException(k+"不存在");
        }
        node.value = v;


    }

    public int getSize() {
        return size;
    }

    public boolean isEmpty() {
        return size==0;
    }
}
